package fun.ticsmyc.question;

import java.util.Comparator;
import java.util.PriorityQueue;

/**
 * @author Ticsmyc
 * @package fun.ticsmyc.question
 * @date 2020-02-25 16:50
 *
 * 一块金条切成两半，是需要花费和长度数值一样的铜板的。比如
 * 长度为20的 金条，不管切成长度多大的两半，都要花费20个铜
 * 板。一群人想整分整块金 条，怎么分最省铜板？
 * 例如,给定数组{10,20,30}，代表一共三个人，整块金条长度为
 * 10+20+30=60. 金条要分成10,20,30三个部分。 如果， 先把长
 * 度60的金条分成10和50，花费60 再把长度50的金条分成20和30，
 * 花费50 一共花费110铜板。
 * 但是如果， 先把长度60的金条分成30和30，花费60 再把长度30
 * 金条分成10和20，花费30 一共花费90铜板。
 * 输入一个数组，返回分割的最小代价。
 *【涉及到两个int相加， 注意越界】
 */
public class 哈弗曼树分隔金条 {

    public static int lessMoney(int[] arr){
        PriorityQueue<Integer> minHeap = new PriorityQueue(new MinheapComparator());

        for(int x: arr){
            minHeap.add(x);
        }

        int res =0;

        while(minHeap.size()>1){
            int temp = minHeap.poll()+minHeap.poll();
            res += temp;
            minHeap.add(temp);
        }
        return res;
    }


    /**
     * 小顶堆
     */
    public static class MinheapComparator implements Comparator<Integer>{

        @Override
        public int compare(Integer o1, Integer o2) {
            return o1-o2;
        }
    }


    /**
     * 大顶堆
     */
    public static class MaxheapComparator implements Comparator<Integer>{

        @Override
        public int compare(Integer o1, Integer o2) {
            return o2-o1;
        }
    }
    public static void main(String[] args) {
        // solution
        int[] arr = { 6, 7, 8, 9 };
        System.out.println(lessMoney(arr));

    }
}
